Global positioning systems (GPSs), handheld devices, and online map routing services provide mechanisms to navigate from one point to another by calculating paths based on information derived from roadway maps. Routing systems typically have usability features to automatically calculate the type of directions desired. The usability features allow an operator to specify routing objectives such as: shortest distance (using an algorithm to determine the shortest distance from one point to the next); least amount of travel time (using an algorithm to determine the shortest distance based on the road's speed limit and distance, and calculating the resulting driving time); least use of freeways; least use of energy (gasoline and/or electricity); and least use of toll roads.
Routing systems (also referred to herein as mapping engines) typically include cartographic maps and map databases to determine an appropriate driving route. The map databases represent a network of roads and often include information about toll roads, speed limits, highway exit points, and points of interest (POIs). The map databases also include points on a map (also known as waypoints) represented in the form of latitudes and longitudes, universal transverse Mercator (UTM) coordinates, and/or geospatial coordinates. Some examples of waypoints include POIs (e.g., museums, restaurants, railways, exit points, etc.), satellites, user-entered destinations, and fixed reference points along a route. These waypoints can be marked on maps in the routing systems.
A route is a series of two or more waypoints. In order to determine a suggested route, a routing system first determines a set of waypoints between a starting point and a destination point. The routing system then guides a user to a nearest waypoint along the route, then to the next waypoint in the route, and so on, until the user reaches the destination point. A typical routing system resolves the starting point and the destination point into its nearest known waypoints on the network and then uses a “great circle routing algorithm” to determine a route between two points. Some routing systems also use a search algorithm to search a graph of nodes (representing waypoints) and edges (representing paths between waypoints). Some examples of search algorithms that can be used to determine a route between two points are Dijkstra's algorithm (to determine the shortest path), an A* algorithm (to determine the shortest path along a weighted graph), and a bi-directional search algorithm.
Routing systems are designed to take into account routing objectives when determining a route between two points. However, a vehicle operator may also be constrained by other factors that impact a range that the vehicle can travel. For example, when selecting POIs, an operator may only have a specified amount of time to travel to the POI. In another example, an operator of an electric vehicle may be looking for a recharge station that is within a selected kilowatt hour (kwHr) range of the current location of the vehicle. Accordingly, it would be desirable to provide a way to determine a range of geographic locations that a vehicle can visit based on both routing objectives and travel constraints.